//https://leetcode.cn/problems/range-sum-query-mutable/?envType=daily-question&envId=2023-11-13


const int N = 30010;

int tr[N];

class NumArray {
private:
    int n;
    vector<int> backup;

    int lowbit(int x) {
        return x & -x;
    }

    void add(int x, int c) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }

    int sum(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr[i];

        return res;
    }
public:
    NumArray(vector<int>& nums) {
        n = nums.size();
        memset(tr, 0, 4 * (n + 1));
        backup = nums;
        for (int i = 0; i < n; i ++) add(i + 1, nums[i]);
    }
    
    void update(int index, int val) {
        int c = backup[index];
        c = val - c;
        add(index + 1, c);
        backup[index] = val;
    }
    
    int sumRange(int left, int right) {
        return sum(right + 1) - sum(left);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 *